import java.util.LinkedList;
import java.util.List;

/**
 * 95. 不同的二叉搜索树 II
 * https://leetcode-cn.com/problems/unique-binary-search-trees-ii/
 */
public class Solutions_95 {
    public static void main(String[] args) {
        int n = 3;  // output: {{1, null, 3, 2}, {3, 2, null, 1},
                    // {3, 1, null, null, 2}, {2, 1, 3}, {1, null, 2, null, 3}}

        List<TreeNode> result = generateTrees(n);
        System.out.println(result);
    }

    public static List<TreeNode> generateTrees(int n) {
        if (n == 0) {
            // 零值判断
            return new LinkedList<>();
        }
        List<TreeNode> res = generateTrees(1, n);
        return res;
    }

    public static List<TreeNode> generateTrees(int start, int end) {
        List<TreeNode> ans = new LinkedList<>();
        if (start >= end) {
            // 空节点，或者只有一个节点
            TreeNode node = start > end ? null : new TreeNode(start);
            ans.add(node);
            return ans;
        }
        // [start, end] 都作为根节点的情况
        for (int i = start; i <= end; i++) {
            // 左子树可能的结构（空子树，也是一个结构）
            List<TreeNode> leftRes = generateTrees(start, i - 1);
            // 右子树可能的结构（空子树，也是一个结构）
            List<TreeNode> rightRes = generateTrees(i + 1, end);
            // 拼接所有可能的结构（两两组装）
            for (TreeNode left : leftRes) {
                for (TreeNode right : rightRes) {
                    // i 作为根节点
                    TreeNode root = new TreeNode(i);
                    root.left = left;
                    root.right = right;
                    ans.add(root);
                }
            }
        }
        return ans;
    }
}


